#include <iostream>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        int s1_count = 0;
        int s2_count = 0;
        int s2_index = 0;
        unordered_map<int, pair<int, int>> store_map;
        pair<int, int> pre_loop, in_loop;
        while (true) {
            s1_count++;
            for (char& c : s1) {
                if (c == s2[s2_index]) {
                    s2_index++;
                    if (s2_index == s2.size()) {
                        s2_index = 0;
                        s2_count++;
                    }
                }
            }
            if (s1_count == n1) {
                return s2_count / n2;
            }
            if (store_map.find(s2_index) != store_map.end()) {
                pre_loop = store_map[s2_index];
                in_loop = {s1_count - pre_loop.first, s2_count - pre_loop.second};
                break;
            } else {
                store_map[s2_index] = {s1_count, s2_count};
            }
        }
        int ans = pre_loop.second + (n1 - pre_loop.first) / in_loop.first * in_loop.second;
        int rest = (n1 - pre_loop.first) % in_loop.first;
        for (int i = 0; i < rest; i++) {
            for (char& c : s1) {
                if (c == s2[s2_index]) {
                    s2_index++;
                    if (s2_index == s2.size()) {
                        s2_index = 0;
                        ans++;
                    }
                }
            }
        }
        return ans / n2;
    }
};